"""
知道二叉数的前序，中序，构建二叉树，元素不重复
"""
class Node():
    def __init__(self, val, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right

    def print_node(self, ):
        # 中
        print(self.val, end=" ")
        # 左
        if self.left:
            self.left.print_node()
        # 右
        if self.right:
            self.right.print_node()
        


def builderTree(root_index, start, end, preorder: list, inorder: list) -> Node:
    # inorder为空，返回None
    if start > end:
        return None

    root_val = preorder[root_index]
    # 在中序中找到root_val的位置
    for i in range(start, end+1):
        if inorder[i] == root_val:
            break

    # 对于inorder,i前面的元素在root的左子树上， 后面的元素在root的右子树上
    left_start = start
    left_end = i - 1
    left_root_index = root_index + 1

    right_root_index = root_index + left_end - left_start + 2
    right_start = i + 1
    right_end = end
    # 初始化节点
    node = Node(root_val)
    node.left = builderTree(left_root_index, left_start, left_end, preorder, inorder)
    node.right = builderTree(right_root_index, right_start, right_end, preorder, inorder)

    return node


preorder = [1, 2, 4, 7, 3, 5, 6, 8]
inorder = [4, 7, 2, 1, 5, 3, 8, 6]

head = builderTree(0, 0, len(preorder)-1, preorder, inorder)
head.print_node()